def partition(arr):
    small = -1
    t = arr[0]
    cur = 0
    for i in range(len(arr)):
        if arr[cur] < t:
            swap(arr, cur, small + 1)
            small += 1
        print(f'l:{arr}  small:{small}  t:{t}  cur:{cur}')
        cur += 1


def swap(arr, a, b):
    arr[a], arr[b] = arr[b], arr[a]


def partition_02(arr):
    s = -1
    b = len(arr)
    t = arr[0]
    i = 0
    while i < b:
        if arr[i] < t:
            swap(arr, i, s + 1)
            s += 1
            i += 1
        elif arr[i] > t:
            swap(arr, i, b - 1)
            b -= 1
        else:
            i += 1
        # print(f'l:{arr}  small:{s}  big:{b}  cur:{i}')
    return arr, s, b


def partition_03(arr, l=0, r=None):
    if r is None:
        r = len(arr) - 1
    s = l - 1
    b = r + 1
    t = arr[l]
    i = l
    while i < b:
        if arr[i] < t:
            swap(arr, i, s + 1)
            s += 1
            i += 1
        elif arr[i] > t:
            swap(arr, i, b - 1)
            b -= 1
        else:
            i += 1
        # print(f'l:{arr}  small:{s}  big:{b}  cur:{i}')
    return s, b


def partition(arr, l, r=None):
    if r is None:
        r = len(arr) - 1
    if l > r:
        print(l, r)
        return
    i, j = partition_03(arr, l, r)
    partition(arr, l, i)
    partition(arr, j, r)


if __name__ == '__main__':
    l = [5, 3, 6, 2, 5, 9, 8]
    # print(l, partition_03(l, 0))
    partition(l, 0)
    print(l)
